Pada masa lampau, Kota Linxia dipanggil Hezhou (Bahasa Cina: 河州), dan kawasan sekitarnya kadang-kala dikenali sebagai Wilayah Hezhou.

Sepanjang sejarahnya, Hezhou sering menjadi persilangan laluan-laluan perdagangan yang penting: salah satu laluan alternatif bagi Laluan Sutera jalan timur, yang menghubungkan kawasan tengah China dengan Asia Tengah, dan laluan utara selatan yang menghubungkan Mongolia dan Tibet. Semasa beberapa masa di zaman Dinasti Song, apabila Xia Barat mengambilalih laluan utara Laluan Sutera, laluan alternatif Didao-Hezhou-Xining di selatan Laluan Sutera menjadi sangat penting, yang menjadikan ketiga-tiga buah kota sebagai pusat perdagangan yang penting. Sejarawan berasa bahawa sejak itu kemudian, semasa era Dinasti Song, orang Islam Hezhou membina masjid pertama mereka.[10]

Tarekat Sufi

Hezhou sudah pun menjadi pusat Islam yang penting pada 1670-an, apabila tuan guru sufi Kashgar Āfāq Khoja melawat masyarakat orang Islam di sempadan barat laut Empayar Qing. Ketika ajarannya di Xining, Didao dan Lanzhou dicatatkan dengan lebih baik, kemungkinan besar dia juga mengajar di Hezhou.[11]Apa pun, anak murid Cina Āfāq Khoja Ma Tai Baba[12] dan seorang lagi tuan guru sufi Cina, Qi Jingyi-pengasas cabang tarekat Qadiriyyah China- dikebumikan di Hezhou.[13] Tempat keramat gongbei di sekeliling kubur mereka di sebelah barat Kota Linxia terus menjadi pusat kesarjanaan Islam yang penting.

Bagaimana pun, anak jati Hezhou dan anak murid Ma Tai Baba yang paling mempunyai harapan, Ma Laichilah yang merevolusikan kehidupan orang Islam barat laut China pada pertengahan kurun ke-18 dengan menjadikan Hezhou sebagai pusat menhuan Hua Si, pertubuhan utama pergerakan sufi Khufiyyah.[14] Tidak lama kemudian, ramai orang dari masyarakat Hui dan Salar terbabit dalam konflik antara pengikut-pengikut Khufiyyah Ma Laichi dengan pengikut-pengikut satu lagi tarekat sufi - Jahriyyah, yang diasaskan pada 1760-an oleh Ma Mingxin. Konflik itu mencapai kemuncaknya pada tahun 1781 apabila tanah Salar di Wilayah Xunhua beberapa kilometer ke barat kota itu dikepung seketika oleh penentang berbangsa Salar yang melaluinya dalam perjalanan ke Lanzhou, dalam satu percaturan yang tidak berjaya untuk menyelamatkan Ma Mingxin daripada penjara.[15]

Pemberontakan dan Perang Minoriti Muslim

Tidak lama selepas permulaan Massive Muslim Armed RebellionPemberontakan Bersenjata Muslim Besar-besaran di barat laut China pada tahun 1862, Hezhou menjadi salah satu kubu kuat bagi penentang beragama Islam yang berjuang menentang Dinasti Qing dan membunuh ramai orang bukan Islam bangsa Han dan Manchu di barat laut China. Pemimpin pemberontakan di kawasan Hezhou ialah Ma Zhan'ao, pemimpin menhuan Huasi yang berpangkalan di Hezhou, sebuah tarekat sufi Khufiyya yang diasaskan seabad yang lalu oleh Ma Laichi.[16] Leftenan teratasnya adalah Ma Haiyan dan Ma Qianling.[17] Seorang pemimpin yang pragmatik, Ma Zhan'ao kelihatannya memilih untuk mengelakkan pertumpahan darah yang keterlaluan; tidak lama selepas menawan kota itu, dia berusaha membolehkan pegawai-pegawai Qing melarikan diri daripada kota penentang itu dengan apa sahaja aset yang mampu dibawa mereka.[16]

Pada lewat 1872, tentera Qing yang diketuai jeneral Zuo Zongtang telah menumpaskan penentang dari kelompok Hui di kawasan-kawasan ke timur Hezhou (Shaanxi and Ningxia), dan mencecah Sungai Tao, yang memisahkan Wilayah Linxia hari ini daripada jiran timurnya, Dingxi. Cubaan Zuo untuk bertapak di barat sungai Tao disentap oleh pejuang Muslim Ma Zhan'ao. Namun Ma sedar bahawa beliau tidak mampu bertahan menentang tentera Qing selama-lamanya, dan pada awal 1873 beliau menghantar anaknya, yang bernama Ma Anliang, ke markas utama Zuo di Anding untuk berunding peralihan sokongan. Bagi menurut perjanjian itu, Ma Zhan'ao menyerahkkan Hezhou kepada tentera kerajaan, menghukum penduduk tempatan yang menentang penyerahan itu, dan dia sendiri menyertai pihak kerajaan untuk berjuang menentang penentang yang berada jauh ke barat. Sebagai balasan, Zuo memberi layanan yang lebih baik kepada mayarakat Islam Hezhou berbanding yang diberikannya kepada orang Ma Hualong di Jinjipu, atau berbanding kumpulan yang mempertahankan Suzhou kemudiannnya pada tahun itu. Muslim Hezhou terselamat daripada pembunuhan beramai-ramai atau pemindahan ke kawasan terpencil; sebaliknya, sebagai isyarat yang unik semasa perang itu, Zuo bertindak mengurangkan ketegangan antara kaum dengan memindahkan sebahagian orang Han tempatan yang bukan Islam dari situ.[16] Meskipun begitu, bagi mengukuhkan kawalan kerajaan ke atas kawasan itu, orang Islam dilarang tinggal di dalam tembok kota Hezhou. Untuk selama beberapa dekad selepas itu, kota bertembok itu kekal menjadi kawasan orang Han bukan Islam, dengan masjidnya diubah menjadi tokong Buddha, manakala orang Islam Hui tinggal dan membina masjid mereka di luar tembok kota itu, khususnya di selatan subbandar Bafang.[18][19]

Ma Zhan'ao sendiri berjuang bersama-sama Zuo Zongtang menentang penentang beragama Islam jauh ke barat. Atas usahanya (dan permintaan Zuo), Ma kemudiannya dianugerahkan dengan "topi berbulu pangkat ke-5" (Cina ringkas: 花翎五品顶戴); keturunannya dan keturunan leftenannya memainkan peranan penting dalam sejarah kawasan ini selama dekad-dekad mendatang.[16]